package com.db.collections;

import java.util.Arrays;

/**
 * This class represents realization of hashMap for primitive type int with emulated chains of collisions
 *
 * @author Alexander Kotov (kotov.alex.22@gmail.com)
 */
public class IntHashMap {

    /**
     * The default initial capacity - MUST be a power of two.
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The multiplier for calculate new capacity while increasing map
     */
    private static final int CAPACITY_MULTIPLIER = 2;

    /**
     * The load factor used when none specified in constructor.
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient private int size;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    private final float loadFactor;
    /**
     * The initial capacity of the hash table.
     *
     * @serial
     */
    final private int initialBucketsCount;

    private int[] keys;

    private int[] values;

    private int[] entries;

    private int[] buckets;

    private int capacity;

    private int bucketsCount;

    private int firstFreeEntry;

    /**
     * Constructs an empty <tt>IntHashMap</tt> with the specified initial with collisions chains
     * capacity and load factor.
     *
     * @param initialBucketsCount the initial capacity
     * @param loadFactor the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *                                  or the load factor is nonpositive
     */
    public IntHashMap(int initialBucketsCount, float loadFactor) {
        if (initialBucketsCount < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialBucketsCount);
        if (initialBucketsCount > MAXIMUM_CAPACITY) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialBucketsCount);
        } else {
            this.initialBucketsCount = initialBucketsCount;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        this.loadFactor = loadFactor;
        clear();
    }

    /**
     * Constructs an empty <tt>IntHashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param initialBucketsCount the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public IntHashMap(int initialBucketsCount) {
        this(initialBucketsCount, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>IntHashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public IntHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    /**
     * @param K specified key
     * @return the value to which the specified key is mapped,
     * or <tt>null</tt> if this map contains no mapping for the key.
     */
    public Integer get(int K) {
        final int index = getBucketIndex(K);
        for (int entry = buckets[index]; entry != -1; entry = getNextEntry(entry)) {
            if (K == keys[entry]) {
                return values[entry];
            }
        }
        return null;
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param K key with which the specified value is to be associated
     * @param V value to be associated with the specified key
     * @return the previous value associated with <tt>K</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>K</tt>.
     */
    public Integer put(int K, int V) {
        if (isNeedResize()) {
            resize(CAPACITY_MULTIPLIER * bucketsCount);
        }
        return placeToMap(K, V);
    }

    /**
     * Removes all of the mappings from this map.
     * The map will be empty after this call returns.
     */
    public void clear() {
        clear(initialBucketsCount);
    }

    /**
     * @return the number of key-value mappings contained in this map.
     */
    public int size() {
        return size;
    }

    /**
     *
     * @param K key
     * @return true if map contains element with key K,
     * false otherwise.
     */
    public boolean contains(int K) {
        final int hashCode = getBucketIndex(K);
        for (int entry = buckets[hashCode]; entry != -1; entry = getNextEntry(entry)) {
            if (K == keys[entry]) {
                return true;
            }
        }
        return false;
    }

    private boolean isNeedResize() {
        return size >= (int) (buckets.length * loadFactor);
    }

    private int getBucketIndex(int value) {
        return value % buckets.length;
    }

    private void resize(int newBucketsCount) {

        int[] curKeys = keys;
        int[] curValues = values;
        int[] curEntries = entries;
        int[] curBuckets = buckets;

        clear(newBucketsCount);

        for (int bucket : curBuckets) {
            if (bucket != -1) {
                placeToMap(curKeys[bucket], curValues[bucket]);
            }
        }
        for (int entry : curEntries) {
            if (entry != -1) {
                placeToMap(curKeys[entry], curValues[entry]);
            }
        }
    }

    private Integer placeToMap(int K, int V) {
        final int bucketIndex = getBucketIndex(K);
        if (buckets[bucketIndex] == -1) {
            final int freeEntry = firstFreeEntry++;
            buckets[bucketIndex] = freeEntry;
            keys[freeEntry] = K;
            values[freeEntry] = V;
            size++;
            return null;
        }
        int index = buckets[bucketIndex];
        for (int entry = index; entry != -1; index = entry, entry = getNextEntry(entry)) {
            if (K == keys[entry]) {
                int result = values[entry];
                values[entry] = V;
                return result;
            }
        }
        final int freeEntry = firstFreeEntry++;
        entries[index] = freeEntry;
        keys[freeEntry] = K;
        values[freeEntry] = V;
        size++;
        return null;

    }

    private int getNextEntry(int entry) {
        return entries[entry];
    }

    private void clear(int initBucketsCount) {
        this.bucketsCount = initBucketsCount;
        capacity = (int) (this.loadFactor * bucketsCount);
        keys = new int[capacity];
        values = new int[capacity];
        entries = new int[capacity];
        buckets = new int [bucketsCount];
        Arrays.fill(buckets, -1);
        Arrays.fill(entries, -1);
        size = 0;
        firstFreeEntry = 0;
    }
}
